
#include "graph.h"


#include<iostream>
#include <QDebug>
#include "queue.h"
#include"interestNode.h"

using namespace std;


template<typename Element>
AMGraph<Element>::AMGraph():vertexNum(0)
{

//    qDebug() << "请输入节点数量，边的数量" ;
//    cin >> vertexNum;
//    cin >> edgeNum;
//    for (int i = 0; i < vertexNum; i++) {
//        qDebug() << "请输入第 "<<i+1<<" 个点的权值：" ;
//        cin >> vertex[i];
//    }
//    for (int i = 0; i < vertexNum; i++)
//        for (int j = 0; j < vertexNum; j++) {
//            edge[i][j] = INT_MAX;			//全部置INT_MAX，表示没有链接
//            if (i == j) edge[i][j] = 0;			//对角线置零
//        }
//    for (int i = 0; i < edgeNum; i++) {
//        qDebug() << "请输入边的顶点（两个）以及边的长度：" ;
//        int v1, v2,distance;
//        cin >> v1; cin >> v2; cin >> distance;
//        edge[v1][v2] = distance;
//    }


    vertex = new Element[MaxSize];
    edge = new int*[MaxSize];

    for (int i = 0; i < MaxSize; ++i) {
        edge[i] = new int[MaxSize]; // 分配每一行的内存
        if (edge[i] == nullptr) {
            qDebug() << "内存分配失败" ;
                // 释放已经分配的内存
                for (int j = 0; j < i; ++j) {
                delete[] edge[j];
            }
            delete[] edge;
            throw "overflow"; // 处理内存分配失败的情况
        }
    }
    path = new int*[vertexNum];
    dist = new int*[vertexNum];
}




template<typename Element>
AMGraph<Element>::AMGraph(bool x)
{

    vertex = new Element[MaxSize];
    edge = new int*[MaxSize];
    for (int i = 0; i < MaxSize; ++i) {

        edge[i] = new int[MaxSize]; // 分配每一行的内存
        if (edge[i] == nullptr) {
            qDebug() << "内存分配失败" ;
            // 释放已经分配的内存
            for (int j = 0; j < i; ++j) {
                delete[] edge[j];
            }
            delete[] edge;
            throw "overflow"; // 处理内存分配失败的情况
        }
    }

    //测试代码1
    if (x == 0)
    {
        qDebug() << "测试参数:\n节点数量为 6，边的数量为5(无向图)" ;
        vertexNum = 6;
        edgeNum = 5;

//        for (int i = 0; i < vertexNum; i++) {
//            qDebug() << "第 " << i + 1 << " 个节点的权值为" << i ;
//            vertex[i] = i;
//        }

        for (int i = 0; i < vertexNum; i++) {
            for (int j = 0; j < vertexNum; j++) {
                edge[i][j] = INT_MAX;			//全部置无穷大，表示没有链接
                if (i == j) edge[i][j] = 0;			//对角线置零
            }
        }
        edge[0][1] = edge[1][0] = 3;
        edge[0][2] = edge[2][0] = 8;
        edge[0][3] = edge[3][0] = 4;
        edge[2][3] = edge[3][2] = 5;
        edge[3][4] = edge[4][3] = 2;

    }

    //测试代码2
    if (x == 1) {
        qDebug() << "测试参数:\n节点数量为 6，边的数量为5（有向图）" ;
        vertexNum = 6;
        edgeNum = 5;
        for (int i = 0; i < vertexNum; i++) {
            qDebug() << "第 " << i + 1 << " 个节点的权值为" << i ;
            vertex[i] = i;
        }
        for (int i = 0; i < vertexNum; i++) {
            for (int j = 0; j < vertexNum; j++) {
                edge[i][j] = INT_MAX;			//全部置INT_MAX，表示没有链接
                if (i == j) edge[i][j] = 0;			//对角线置零
            }
        }
        edge[0][1] = 3;
        edge[0][2] = 8;
        edge[0][3] = 4;
        edge[2][3] = 5;
        edge[3][4] = 2;
    }

}



template<typename Element>
void AMGraph<Element>::bfTraverse(int v)	//从第v个节点开始
{
    //声明“访问标记”数组（动态），为了递归方便，作为static类型
    bool* visited;          //话说为啥不直接private【哭笑】（可优化）
    visited = new bool[vertexNum];

    for (int i = 0; i < vertexNum; i++)
        visited[i] = false;

    lqueue<int> q;
    qDebug() << vertex[v - 1];		//数组下标和计数的关系

    visited[v - 1] = true;  //因为是从第v个节点开始

    q.in(v - 1);

    while (!q.isEmpty()) {	//遍历的主要部分
        int x = q.out();		//从队列中拿出一个元素
        for (int i = 0; i < vertexNum; i++) {	//对图中的所有元素进行遍历
            if (edge[x][i] >0 && visited[i] != true) {	//若两个顶点之间有边 且 另一个顶点没有被访问过
                visited[i] = true;	//打上访问标记
                qDebug() << vertex[i];	//访问
                q.in(i);			//加入队列
            }						//继续遍历，直到检查完这个顶点和图中所有点的边
        }
    }

    //多分量检查
    for (int k = 0; k < vertexNum; k++) { //检查所有顶点
        if (visited[k] != true) {			//若有顶点未被访问过，说明不止1，则重复上述遍历操作

            qDebug() << vertex[k];		//数组下标和计数的关系

            visited[k] = true;

            q.in(k);

            while (!q.isEmpty()) {	//遍历的主要部分
                int x = q.out();		//从队列中拿出一个元素
                for (int i = 0; i < vertexNum; i++) {	//对图中的所有元素进行遍历
                    if (edge[x][i] != INT_MAX && visited[i] != true) {	//若两个顶点之间有边 且 另一个顶点没有被访问过
                        visited[i] = true;	//打上访问标记
                        qDebug() << vertex[i];	//访问
                        q.in(i);			//加入队列
                    }						//继续遍历，直到检查完这个顶点和图中所有点的边
                }
            }
        }
    }
    delete[] visited;
}



template<typename Element>
void AMGraph<Element>::dfTraverse(int v) //从编号为v的结点开始遍历，对应的数组下标为v-1；
{
    //定义访问标志
    static bool* visited;  //为了递归（可优化）
    visited = new bool[vertexNum];

    //初始化访问标记
    for (int i = 0; i < vertexNum; i++)
        visited[i] = false;



    dfTraverse(visited, v - 1);			//实现函数，输入访问标志数组和待开始节点的下标值

    //多分量检查
    for (int i = 0; i < vertexNum; i++)
        if(	visited[i] == false)
            dfTraverse(visited,i);
}

template<typename Element>
void AMGraph<Element>::getEdge(int** &edge2)
{
    for (int i=0; i < vertexNum; i++)
        for (int j=0; j < vertexNum; j++)
        {
            edge2[i][j] = edge[i][j];

        }
}

template<typename Element>
Element* AMGraph<Element>::getVertex(){
    return vertex;
}


template<typename Element>
int AMGraph<Element>::getVertexNum()
{
    return vertexNum;
}

template<typename Element>
int AMGraph<Element>::getEdgeNum()
{
    return edgeNum;
}


template<typename Element>
int AMGraph<Element>::inZero()
{
    int x = 0;	//目标点计数

    for (int j = 0; j < vertexNum; j++) {	//按列检索
        //只是实现记录度为0的顶点话可以直接bool,不过这样也方便后续记录不为0的
        int count = 0;	//边计数

        for (int i = 0; i < vertexNum; i++) {	//检查当前列的每一行
            if (edge[i][j] > 0) count++;		//对到达该结点的边计数
        }
        if (count == 0) x++;
    }

    return x;
}


template<typename Element>
int AMGraph<Element>::outZero()	//出度为0
{
    int x = 0;	//目标点计数
    for (int i = 0; i < vertexNum; i++) {	//按行检索
        int count = 0;	//边计数
        for (int j = 0; j < vertexNum; j++) {	//检查当前行的每一列
            if (edge[i][j] > 0) count++;		//对从该结点出发的边计数
        }
        if (count == 0) x++;
    }
    return x;
}


template<typename Element>
void AMGraph<Element>::addVertex(Element newData){

    //分配更多内存空间
    if( vertexNum + 1 > MaxSize)  MaxSize=+10;

    Element* newVertex = new Element[MaxSize];

    int** newEdge = new int*[MaxSize];

    for (int i = 0; i < MaxSize; ++i) {

        newEdge[i] = new int[MaxSize]; // 分配每一行的内存

        if (newEdge[i] == nullptr) {
            qDebug() << "内存分配失败" ;
            // 释放已经分配的内存
            for (int j = 0; j < i; ++j) {
                delete[] newEdge[j];
            }
            delete[] newEdge;
            throw "overflow"; // 处理内存分配失败的情况
        }
    }

    //把之前新的数据添加进来
    for(int i = 0;i<vertexNum;i++){
        newVertex[i] = vertex[i];
        for(int j = 0;j<vertexNum;j++)
            newEdge[i][j] = edge[i][j];
    }

    //新增一个点
    vertexNum++;

    //邻接矩阵初始化
    for(int i = 0;i<vertexNum;i++)
        newEdge[i][vertexNum-1] = 0;

    for(int j = 0;j<vertexNum;j++)
        newEdge[vertexNum-1][j] = 0;
    //点的个数增加一个



    //（疑问）
    //把新的点添加进来
    newVertex[vertexNum].id = newData.id;
    newVertex[vertexNum].myPoi = newData.myPoi;
        qDebug()<<"newVertex poi:"<<newVertex[vertexNum].myPoi;
    newVertex[vertexNum].name = newData.name;
    newVertex[vertexNum].inf = newData.inf;
    //存储新的数据，释放旧的内存（注意要把旧内存的地址保留下来，同时继承了新的之后不可以把新的删了）
    Element* tempVertex = vertex;
    int** tempEdge = edge;
    vertex = newVertex;
    edge = newEdge;
    delete[] tempVertex;
    for (int i = 0; i < MaxSize; ++i) {
        delete[] tempEdge[i];
    }
}

template<typename Element>
void AMGraph<Element>::addEdge(int src,int dest,int length){
    if(edge[src][dest] >0) qDebug()<<"边已经存在";
    else edge[src][dest] = length;
}

template<typename Element>
void AMGraph<Element>::deleteEdge(int src,int dest){
    if(edge[src][dest] ==0) qDebug()<<"不存在边";
    else edge[src][dest] = 0;
}

template<typename Element>
void AMGraph<Element>::deleteVertex(int index){

    //删除该节点的边
    //默认为无向图，选择行/列遍历一次，减少边计数
    for(int i = 0;i<vertexNum;i++)
        if(edge[i][index] >0) edgeNum--;


    //移动边矩阵（对边进行处理）
    //把右边部分的边移过来
    for(int i = 0;i<vertexNum-1;i++)
        for(int j = index;j<vertexNum-1;j++)
        edge[i][j] = edge[i][j+1];    
    //把下面部分的边往上移
    for(int j = 0;j<vertexNum-1;j++)
        for(int i = 0;i<vertexNum-1;i++)
        edge[i][j] = edge[i+1][j];


    //移动节点数组，覆盖该节点（对点进行处理）
    for(int i = index;i<vertexNum-1;i++)
        vertex[i] = vertex[i+1];


    //更新点数量
    vertexNum --;
}


//dfTraverse辅助函数
template<typename Element>
void AMGraph<Element>::dfTraverse(bool* visited, int x)//通过指针共用同一个访问标志数组，x是要访问节点的下标
{
    //输出当前节点，并打上标记
    qDebug() << vertex[x];
    visited[x] = true;
    //实现递归的主要内容
    for (int i = 0; i < vertexNum; i++) {
        //qDebug() << "当前节点的visted为：" << visited[i] ;
        if (edge[x][i] != INT_MAX && visited[i] == false) dfTraverse(visited,i);
    }
}



template<typename Element>
void AMGraph<Element>::inquire(Element serialNumber)//查询顶点信息
{
    for(int i=0;i<vertexNum;i++){
        if(serialNumber == i + 1){
         qDebug()<<vertex[i].name;//输出景点信息
         qDebug()<<vertex[i].inf;//输出景点信息
        }
    }
}


//可以继续（1）
template<typename Element>
void AMGraph<Element>::Floyd() {

    //path 是一个二维动态数组，用于存储最短路径上的中间节点。
    //dist 是一个二维动态数组，用于存储两点间的最短距离。
    //    int** path = new int*[vertexNum]; // 用于存储最短路径上的中间节点
    //    int** dist = new int*[vertexNum]; // 用于存储两点间的最短距离

    // 初始化path和dist数组

    for (int i = 0; i < vertexNum; i++)
    {
        //每一行进行操作
        path[i] = new int[vertexNum];
        dist[i] = new int[vertexNum];//（距离）

        for (int j = 0; j < vertexNum; j++)
        {

        dist[i][j] = edge[i][j]; // 初始化dist为邻接矩阵的值

        if (dist[i][j] != INT_MAX && i != j)//有权重
        {
                path[i][j] = i; // 初始化path为起始点到终点的路径上的中间节点
        } else {
                path[i][j] = INT_MAX; // 若不存在路径，则表示为INT_MAX
        }
        }
    }

    // Floyd算法核心步骤
    for (int k = 0; k < vertexNum; k++) {
        for (int i = 0; i < vertexNum; i++) {
        for (int j = 0; j < vertexNum; j++) {
                //表示 int 类型的最大值。
                //k是中转
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[k][j]; // 更新最短路径上的中间节点
                }
        }
        }
    }
    printFloyd();

}


template<typename Element>
void AMGraph<Element>::printEdge(){
    for (int i = 0; i < vertexNum; i++)
    {
        for (int j = 0; j < vertexNum; j++) {
        cout<<edge[i][j]<<"\t";
        }
        cout<<endl;
    }
}


template<typename Element>
void AMGraph<Element>::printFloyd(){
    // 输出最短路径和最短距离
    for (int i = 0; i < vertexNum; i++) {
        for (int j = 0; j < vertexNum; j++) {
        if (i != j) {
                qDebug() << "Vertex " << i << " to Vertex " << j << ": ";
                if (path[i][j] != INT_MAX) {
                    int next = j;
                    qDebug() << i << " ";
                    while (next != i)//循环未结束说明还要继续点
                    {
                        qDebug() << " -> " << next << " ";
                        next = path[i][next];
                    }
                } else {
                    qDebug() << "No path";
                }
                qDebug() << " (distance: " << dist[i][j] << ")" ;
        }
        }
    }
}



template<typename Element>
void AMGraph<Element>::printVertexPoi(){
    for(int i=0;i<vertexNum;i++){
        qDebug()<<vertex[i].myPoi;
    }
}



//数据库函数
template<typename Element>
int  AMGraph<Element>::databasePreprocessing(){



    // 连接到数据库
    QSqlDatabase db = QSqlDatabase::addDatabase("QSQLITE");
    db.setDatabaseName("campusMap.db");

    if (!db.open()) {
        qDebug() << "无法打开数据库";
        return 1;
    }

    // 创建表1
    QSqlQuery query(db); // 将数据库连接与查询对象关联

    if (!query.exec("CREATE TABLE IF NOT EXISTS Table1 (id INT, name TEXT, inf TEXT, x REAL, y REAL,PRIMARY KEY (id))")) {
        qDebug() << "创建表1出错: " << query.lastError().text();
    } else {
        qDebug() << "成功创建表1";
    }

    // 创建表2，使用三元组表示稀疏矩阵edge
    if (!query.exec("CREATE TABLE IF NOT EXISTS Table2 (rowIndex INT, colIndex INT, edgeValue REAL, PRIMARY KEY (rowIndex, colIndex))")) {
        qDebug() << "创建表2出错: " << query.lastError().text();
    } else {
        qDebug() << "成功创建表2";
    }

    // 关闭数据库连接
    db.close();
    qDebug()<<"关闭数据库连接";


}


template<typename Element>
int AMGraph<Element>::insertVertexIntoTable1(const Element& vertex) {
    QSqlDatabase db = QSqlDatabase::database();  // 获取现有的数据库连接
    if (!db.isValid()) {
        qDebug() << "数据库连接无效";
        return 1;
    }

    QSqlQuery query(db);

    QString insertQuery = "INSERT INTO Table1 (id, name, inf, x, y) VALUES (:id, :name, :inf, :x, :y)";
    query.prepare(insertQuery);
    query.bindValue(":id", vertex.id);
    query.bindValue(":name", vertex.name);
    query.bindValue(":inf", vertex.inf);
    query.bindValue(":x", vertex.myPoi.x());
    query.bindValue(":y", vertex.myPoi.y());

    if (!query.exec()) {
        qDebug() << "插入表1时出错:" << query.lastError().text();
                                              return 1;
    } else {
        qDebug() << "成功插入表1";
    }

    return 0;
}

template<typename Element>
int AMGraph<Element>::insertEdgeIntoTable2(int rowIndex, int colIndex, int edgeValue) {
    QSqlDatabase db = QSqlDatabase::database();  // 获取现有的数据库连接
    if (!db.isValid()) {
        qDebug() << "数据库连接无效";
        return 1;
    }

    QSqlQuery query(db);

    QString insertQuery = "INSERT INTO Table2 (rowIndex, colIndex, edgeValue) VALUES (:rowIndex, :colIndex, :edgeValue)";
    query.prepare(insertQuery);
    query.bindValue(":rowIndex", rowIndex);
    query.bindValue(":colIndex", colIndex);
    query.bindValue(":edgeValue", edgeValue);

    if (!query.exec()) {
        qDebug() << "插入表2时出错:" << query.lastError().text();
                                              return 1;
    } else {
        qDebug() << "成功插入表2";
    }

    return 0;
}




